package org.example.sword2offer.primary;

import java.util.HashMap;
import java.util.LinkedHashSet;

/**
 * @author: lynn
 * @Descript: leetcode460 lfu (Least frequency Used 最不经常使用)
 * 如果使用评率是一样的，那么需要把最早使用的剔除掉，所以有 cacheKey，useCount，useTime 这三个参数
 * 追求时间快速，那么就需要hashMap或者 hashSet
 * @date: 2021/5/23 21:42
 * @version: 1.0
 */
public class Q65_LFUCache {

     private int min;

     private int capacity;

     private HashMap<Integer,Integer> keyToVal;

     private HashMap<Integer,Integer> keyToCount;

     //LinkedHashSet 类似于一个队列，新来的值排在前面，重点是保证时间上的一个顺序
     private HashMap<Integer, LinkedHashSet<Integer>> countToLruKeys;


    public Q65_LFUCache(int capacity) {
        this.min = -1;
        this.capacity = capacity;
        this.keyToVal = new HashMap<>();
        this.keyToCount = new HashMap<>();
        this.countToLruKeys = new HashMap<>();
    }

    public int get(int key){
        if (!keyToVal.containsKey(key)) return -1;
        int count=keyToCount.get(key);
        countToLruKeys.get(count).remove(key);
        if (count==min && countToLruKeys.get(count).size()==0) min++;
        putCount(key,count+1);
        return keyToVal.get(key);
    }

    public void put(int key,int value){
        if (capacity<=0) return;

        //更新
        if (keyToVal.containsKey(key)){
            keyToVal.put(key,value);
            int count=keyToCount.get(key);
            countToLruKeys.get(count).remove(key);
            if (count==min && countToLruKeys.get(count).size()==0) min++;
            putCount(key,count+1);
            return;
        }
        if (keyToVal.size()>=capacity)
            //删除最少使用的
            evict(countToLruKeys.get(min).iterator().next());

        min=1;
        putCount(key,min);
        keyToVal.put(key,value);
    }

    //把最少使用的给去掉
    private void evict(int key){
        countToLruKeys.get(min).remove(key);
        keyToVal.remove(key);
    }
    //count =count +1; 更新的同时，使用次数也加1
    private void putCount(int key,int count){
        keyToCount.put(key,count);
        countToLruKeys.putIfAbsent(count,new LinkedHashSet<>());
        countToLruKeys.get(count).add(key);
    }


    public static void main(String[] args) {
        Q65_LFUCache lfu=new Q65_LFUCache(2);
        lfu.put(1,1);
        lfu.put(2,2);
        System.out.println(lfu.get(1));
        lfu.put(3,3);
        System.out.println(lfu.get(2));
        System.out.println(lfu.get(3));
        lfu.put(4,4);
        lfu.get(1);
        lfu.get(3);
        lfu.get(4);
    }
}
